"""support fcts to convert binary trees to lattice coordinates
the lattice is defined as a circular grid acc. to [1]"""

import math
import types

def parseTreeToLattice(tree, rootLabel=1):
    """returns the lattice labels for a binary tree"""
    coords = [rootLabel]
    if type(tree) == types.ListType:
        coords += parseTreeToLattice(tree[1], rootLabel*2)
        coords += parseTreeToLattice(tree[2], rootLabel*2+1)
    return coords


def calcPolarCoords(k):
    """calculates the polar coordinates from a lattice label
    is atuple with radius and angle (in rad)"""
    if k == 1:
        return (0,0)
    else:
        r = math.floor(math.log(k)/math.log(2))
        phi = math.pi*(1./2+1./2**r+k%2**r/2**(r-1))
        ##phi = phi/math.pi*180
        return (r,phi)


def convertToXYGrid(polar, rscaling, offset):
    """calculates XY coordinates for e.g. screen output with
    respect to (0,0) offset and scaling, polar is a tuple with
    (radius,angle[rad]), rsaling a radius scaling factor and offset
    is added to x,y coordinates"""
    x = polar[0]*rscaling*math.cos(polar[1])+offset
    y = polar[0]*rscaling*math.sin(polar[1])+offset
    return (x,y)


if __name__ == '__main__':
    print "test parseTreeToLattice"
    gp1 = ['+', 1, 2]
    lb1 = parseTreeToLattice(gp1)
    gp2 = ['+',['+',1,2],3]
    lb2 = parseTreeToLattice(gp2)
    gp3 = ['+', ['+', 91, 92], ['+', 93, 94]]
    lb3 = parseTreeToLattice(gp3)

    pass
